package list

import (
	"fmt"
	"gitee.com/kklt1996/data-structure/common"
	"strings"
)

/*
	双向节点
*/
type twoWayNode struct {
	// 节点的值
	value interface{}
	// 下一个元素的指针
	next *twoWayNode
	// 上一个元素的指针
	prev *twoWayNode
}

/*
	打印node
*/
func (node twoWayNode) String() string {
	return fmt.Sprint(node.value)
}

/*
	循环双向链表
	当只存在头节点,尾部节点,虚拟节点的时候:
	头节点在虚拟节点之后 head = dummyNode.next, head.prev = dummyNode
	尾部节点在虚拟节点之前 tail = dummyNode.prev, tail.next = dummyNode
	尾部节点在头节点之后 head.next = tail, tail.prev = head
	双向链表的优势是双端插入都是O(1)的时间复杂度,可用于构建双端队列
*/
type LoopList struct {
	dummyNode *twoWayNode
	size      int
}

/*
	获取链表的大小
*/
func (loopList LoopList) GetSize() int {
	return loopList.size
}

/*
	获取链表是否为空
	当虚拟节点的头部和尾部为空的时候，表示循环链表为空
*/
func (loopList LoopList) IsEmpty() bool {
	return loopList.dummyNode.next == nil && loopList.dummyNode.prev == nil
}

/*
	O(n)
	添加元素
*/
func (loopList *LoopList) Add(index int, value ...interface{}) error {
	// 检查index
	if index < 0 || index > loopList.size {
		return common.IndexError{}
	}
	// 要插入的内容为空的话直接返回成功
	if len(value) == 0 {
		return nil
	}
	// 链接要插入的链表
	insertHead, insertTail := linkedTwoWayNode(value)
	// 获取索引之前的节点
	prevNode := loopList.node(index - 1)
	// 在节点之后链接链表
	insertAfter(prevNode, loopList.dummyNode, insertHead, insertTail)
	// 变更元素个数
	loopList.size += len(value)
	return nil
}

/*
	O(len(value))
	在头部添加元素
*/
func (loopList *LoopList) AddFirst(value ...interface{}) {
	_ = loopList.Add(0, value...)
}

/*
	O(len(value))
	在头部添加元素
*/
func (loopList *LoopList) AddLast(value ...interface{}) {
	_ = loopList.Add(loopList.size, value...)
}

/*
	O(n/2)
	获取某个位置的元素
*/
func (loopList LoopList) Get(index int) (interface{}, error) {
	if index < 0 || index > loopList.size-1 {
		return nil, common.IndexError{}
	}
	// index+1 = 1~size, node = 0~(size-1)
	return loopList.node(index).value, nil
}

/*
	O(1)
*/
func (loopList LoopList) GetFirst() (interface{}, error) {
	return loopList.Get(0)
}

/*
	O(1)
*/
func (loopList LoopList) GetLast() (interface{}, error) {
	return loopList.Get(loopList.size - 1)
}

/*
	O(n/2)
	设置某个索引的位置节点的值
*/
func (loopList *LoopList) Set(index int, value interface{}) error {
	if index < 0 || index > loopList.size-1 {
		return common.IndexError{}
	}
	// 查找元素.因为有索引校验,node一定不等于nil
	node := loopList.node(index)
	node.value = value
	return nil
}

/*
	O(n/2)
	根据索引删除节点
*/
func (loopList *LoopList) Remove(index int) (interface{}, error) {
	if index < 0 || index > loopList.size-1 {
		return nil, common.IndexError{}
	}
	// 查找节点
	node := loopList.node(index)
	// 删除节点
	value := loopList.removeNode(node)
	return value, nil
}

func (loopList *LoopList) RemoveFirst() (interface{}, error) {
	return loopList.Remove(0)
}

func (loopList *LoopList) RemoveLast() (interface{}, error) {
	return loopList.Remove(loopList.size - 1)
}

/*
	根据元素值删除第一个元素
*/
func (loopList *LoopList) RemoveElement(value interface{}) {
	for node := loopList.dummyNode.next; node != nil && node != loopList.dummyNode; {
		if node.value == value {
			loopList.removeNode(node)
			break
		} else {
			node = node.next
		}
	}
}

/*
	根据条件删除元素
*/
func (loopList *LoopList) RemoveIfMatch(matchFunc func(value interface{}) bool) int {
	removeNum := 0
	for node := loopList.dummyNode.next; node != nil && node != loopList.dummyNode; {
		// 先获取下一个节点,避免node节点被删除的时候无法正确获取下一个节点
		nextNode := node.next
		if matchFunc(node.value) {
			loopList.removeNode(node)
			removeNum++
		}
		node = nextNode
	}
	return removeNum
}

/*
	删除值为value的全部元素
*/
func (loopList *LoopList) RemoveAllElement(value interface{}) int {
	return loopList.RemoveIfMatch(func(nodeValue interface{}) bool {
		return nodeValue == value
	})
}

/*
	检查是否包含某个元素
*/
func (loopList LoopList) Contains(value interface{}) bool {
	for node := loopList.dummyNode.next; node != nil && node != loopList.dummyNode; node = node.next {
		if node.value == value {
			return true
		}
	}
	return false
}

/*
	对链表进行循环
*/
func (loopList *LoopList) Foreach(foreachFunc func(index int, value interface{}) bool) {
	index := 0
	for node := loopList.dummyNode.next; node != nil && node != loopList.dummyNode; node = node.next {
		if foreachFunc(index, node.value) {
			break
		}
		index++
	}
}

/*
	可以删除和设置节点值的迭代器
*/
func (loopList *LoopList) Iterator(iteratorFunc func(iterator common.Iterator) bool) {
	loopListIterator := &LoopListIterator{loopList: loopList}
	var iterator common.Iterator = loopListIterator
	for node := loopList.dummyNode.next; node != nil && node != loopList.dummyNode; {
		loopListIterator.node = node
		loopListIterator.removeFlag = false
		// 先获取下一个节点,避免node节点被删除的时候无法正确获取下一个节点
		nextNode := node.next
		if iteratorFunc(iterator) {
			break
		}
		// 处理下一个节点
		node = nextNode
	}
}

func (loopList *LoopList) ToSlice() []interface{} {
	res := make([]interface{}, 0, loopList.size)
	for node := loopList.dummyNode.next; node != nil && node != loopList.dummyNode; node = node.next {
		res = append(res, node.value)
	}
	return res
}

func (loopList LoopList) String() string {
	var res string
	// 循环链表遍历完成的条件是返回到头结点,且不是空链表
	for cur := loopList.dummyNode.next; cur != nil && cur != loopList.dummyNode; cur = cur.next {
		res += fmt.Sprintf("%v<=>", cur.value)
	}
	res = strings.TrimSuffix(res, "<=>")
	return res
}

/*
	删除节点
*/
func (loopList *LoopList) removeNode(node *twoWayNode) interface{} {
	// 获取值,直接前驱,直接后继节点
	value := node.value
	prevNode := node.prev
	nextNode := node.next
	// 删除节点
	// 检查直接前驱和直接后继节点是相等(是否删除完成之后只剩下dummyNode),避免dummyNode独自成环
	if prevNode == nextNode {
		// 重置循环链表
		loopList.dummyNode.next = nil
		loopList.dummyNode.prev = nil
	} else {
		// 原节点直接前驱和直接后继进行链接
		prevNode.next = nextNode
		nextNode.prev = prevNode
	}
	// 删除已经删除的节点关系
	node.value = nil
	node.prev = nil
	node.next = nil
	// 修改链表个数
	loopList.size--
	return value
}

/*
	获取第index个节点 index=[-1,size-1]
*/
func (loopList *LoopList) node(index int) *twoWayNode {
	// 排除loopList.dummyNode.next和loopList.dummyNode.prev为空的情况
	if loopList.size == 0 {
		return loopList.dummyNode
	}
	var node *twoWayNode
	if index < (loopList.size >> 1) {
		// 假定第-1个元素是loopList.dummyNode
		// 在dummyNode.next寻找prevNode
		// i=-1　　　prevNode是第-1个元素
		// i=index-1 prevNode是第index-1个元素
		// i=size-1  prevNode是第size-1个元素
		node = loopList.dummyNode
		for i := -1; i < index; i++ {
			node = node.next
		}
	} else {
		// 假定第-1个元素是loopList.dummyNode
		// 从尾部节点开始,向前寻找元素
		// i=size-1  prevNode是第size-1个元素,也就是loopList.dummyNode.prev
		// i=index-1 prevNode是第index-1个元素
		// i=-1      prevNode是第-1个元素
		node = loopList.dummyNode.prev
		for i := loopList.size - 1; i > index; i-- {
			node = node.prev
		}
	}
	return node
}

/*
	在节点之后插入元素
*/
func insertAfter(prevNode *twoWayNode, dummyNode *twoWayNode, insertHead *twoWayNode, insertTail *twoWayNode) {
	next := prevNode.next
	// 只有当只有一个虚拟节点的时候,next才可能为空
	if next == nil {
		next = dummyNode
	}
	// 头部和直接前驱进行链接
	prevNode.next = insertHead
	insertHead.prev = prevNode
	// 尾部和直接后继链接
	insertTail.next = next
	next.prev = insertTail
}

/*
	将节点链接成双向链表
*/
func linkedTwoWayNode(value []interface{}) (*twoWayNode, *twoWayNode) {
	//　链接节点
	var insertHead *twoWayNode
	var insertTail *twoWayNode
	for _, v := range value {
		if insertTail == nil {
			insertTail = &twoWayNode{prev: nil, value: v, next: nil}
			insertHead = insertTail
		} else {
			insertTail.next = &twoWayNode{prev: insertTail, value: v, next: nil}
			insertTail = insertTail.next
		}
	}
	return insertHead, insertTail
}

/*
	loopList迭代器,用于再遍历的过程中删除元素和修改元素
*/
type LoopListIterator struct {
	loopList   *LoopList
	node       *twoWayNode
	removeFlag bool
}

/*
	删除节点
*/
func (iterator *LoopListIterator) Remove() {
	if iterator.removeFlag {
		return
	}
	// 删除节点
	iterator.loopList.removeNode(iterator.node)
	iterator.removeFlag = true
}

/*
	修改节点的值
*/
func (iterator LoopListIterator) Set(value interface{}) error {
	if iterator.removeFlag {
		return common.OperatorNotUseful{}
	}
	iterator.node.value = value
	return nil
}

/*
	获取value
*/
func (iterator LoopListIterator) Get() (interface{}, error) {
	if iterator.removeFlag {
		return nil, common.OperatorNotUseful{}
	}
	return iterator.node.value, nil
}
